A multi-station data network includes a plurality of stations connected to a common medium for communication. Communication networks usually have many variable parameters, such as changing station activity, varying average load, and bursty traffic. Additionally, from time to time the network topology may be changed. For example, new modes and channels can appear, some nodes can be switched off, some channels can be interrupted, and channel speed or length may change.
Communication networks commonly operate under changeable conditions. For example, network load, nodes activity, network topology, inter-node distances, channel speed and other network parameters typically change with time. Bursty traffic is transmitted in many networks. While some nodes have long sequences of packets other nodes have no messages at all. New stations or hubs can be added in the network. For example, some nodes can be permanently or temporarily switched off, channel or node failures can change network topology, etc. Network load and traffic are, in general, random variables whose average value depends on the time of day, day of week, etc. Even in stable networks, it is desirable to use adaptive mechanisms at the time of network initialization to implement plug-and-play technology or in order to simplify network management.
To coordinate transmission over a common medium by the stations of the network, communications on the network typically follow a prescribed multiple access technique or protocol. Such protocols determine the sequence of actions to be performed by each station to avoid or reduce the impact of interference arising from transmission of other stations.
Multi-station networks may have different topologies. Common topologies include the multi-hub network shown in FIG. 1. FIG. 1 is a prior art network topology comprising a plurality of hubs 10, a plurality of stations 15 and a plurality of full duplex channels 11 for inter-node communication. FIG. 2 shows a prior art head-end networks topology comprising a head end 20, two unidirectional wired or wireless channels for transmitting from the head-end to station 21, and from the stations to the head-end 22. FIG. 3 shows a prior art wired or wireless bus-topology network, comprising a set of stations 35, interconnected each other by a bi-directional channel 30. Data transmission in the networks shown in FIGS. 1-3 is coordinated by a multiple access technique or protocol which determines the sequence of actions to be performed by each node to avoid or reduce the impact of interference due to transmission by other nodes.
Conventional communication protocols and multiple access techniques have the common drawbacks that they do not provide an efficient means for collision-free data transmission with automatic adaptation to changing network conditions. This reduces the potential network efficiency because in common network situations there is random network traffic and node activity, variable distances between nodes, and variable data transmission speed.
Networks with a ring topology commonly use a token-ring multiple access. Networks based on a bus topology sometime use a token-bus multiple access. Token access techniques for networks with bus topology (such as that described by IEEE standard 802.4) or ring topology (such as that described by IEEE standard 802.5 or FDDI) are collision free but they require transmission of control information (tokens) from one network station to another. When the token is distorted a complex token-recovery procedure has to be performed, what is the major limitation of token access techniques. Access management procedures in local area networks with token access are comparatively complicated and implementation of such networks requires high investments.
To avoid collisions in high-speed local area networks the Demand Priority Protocol (DPP) was proposed for the IEEE 802.12 standard. This protocol is applicable in networks with star or tree topology consisting of one or more interconnected hubs and a plurality of network stations connected to the hubs. The hubs perform a round-robin poll to all connected stations or lower-level hubs.
While the DPP protocol is collision-free, one drawback of the DPP protocol is that the implementation of a polling algorithm tends to cause a loss of network throughput. This is because in large multi-level tree networks the protocol tends to be complex and requires a correspondingly complex network management system. Moreover, the DPP algorithm cannot be implemented on a conventional network with a bus topology. The polling technique of the DPP protocol requires all network nodes to be polled in each polling cycle. A major drawback of the DPP algorithm is that it does not automatically adapt for changes in node activity, network distances, or speed of transmission.
Networks which rely on the bus topology commonly use the Carrier Sense Multiple Access with Collision Detection (CSMA/CD) protocol. An example of the CSMA/CD protocol is disclosed in U.S. Pat. No. 4,063,220 issued on Dec. 13, 1988 to Metcalfe, et al. In accordance with the CSMA/CD protocol, whenever any network station has a packet for transmission, it senses the communication medium, and if the medium is quiescent, the packet is impressed on the network. If the medium is engaged, the station waits and transmits its packet when it detects that the medium is idle. In view of the signal propagation delay in the medium, it is possible that two or more stations may start transmitting on the medium almost simultaneously. These transmissions may become scrambled and a collision may appear in the network. Any packets that have collided must be retransmitted. While the CSMA/CD protocol does facilitate the successful transmission of data between network stations, a considerable amount of time and medium throughput is lost whenever a collision occurs. Collision probability increases with traffic load, transmission rate or network length. An increased collision probability results in a longer packet transmission delay. Consequently, the CSMA/CD protocol can not be used for real-time transmission of multimedia information. Moreover, the CSMA/CD protocol does not have any means for adaptation to network traffic, node activity, network distances or speeds of transmission.
One technique to improve the efficiency of CSMA/CD is disclosed in U.S. Pat. No. 4,628,311, issued Dec. 12, 1986 to Milling. The technique of U.S. Pat. No. 4,628,311 assigns to each station an access window within a predetermined response period after the medium becomes idle. To distribute transmission capacity among the stations the access windows assigned to all stations are rotated to give all stations essentially equal access to the medium. Although this protocol is entitled Carrier-Sense Multiple-Access with Collision Avoidance (CSMA/CA), the inventor believes that the CSMA/CA protocol is unable to eliminate collisions altogether. The CSMA/CA protocol requires transmitting access control information to rotate the access windows. To achieve that, each frame has to contain in its header a window rotation control field. When a frame is distorted by unavoidable transmission errors, the network stations lose window rotation control information, which may lead to collisions. There are also other drawbacks to CSMA/CA protocol. Since the frame header has to be modified, a CSMA/CA network cannot use standard frame formats such as the Ethernet format. Additionally, the CSMA/CA protocol does not provide any means for adaptation to changing network conditions.
Another collision avoidance scheme which assigns to each station an access window for determining the beginning of transmission after the medium becomes idle is disclosed in U.S. Pat. No. 4,799,052, issued Jan. 17, 1989 to Near, et al. According to the teachings of U.S. Pat. No. 4,799,052 the time period between the instant the medium is released and the access window of a given station depends on the station's unique medium address number and also upon the medium address number of the station which was the last to transmit before the medium became idle. However, this method also requires access control information to be passed in the network to determine whether or not a given station may send its packet. This information defines the medium address number of the station, which is transmitting a frame. All frame headers must therefore have to include a special control field for the medium address number of the transmitting station. Similar to the previous scenario, standard frames such as the Ethernet frame cannot be used with this frame format. Moreover, as in the previous scenario, the receiving station loses access control information if the frame is distorted in transmission, and recovery requires a special procedure. The method of U.S. Pat. No. 4,799,052 does not provide any means for adaptation to current state of the network.
U.S. Pat. No. 5,576,702, issued Nov. 19, 1996 to Samoylenko, provides a means for collision-free, Ethernet-compatible multiple access without transmitting any access control information in data frames. However, a drawback of the method of U.S. Pat. No. 5,576,702 is that it does not have any mechanism for automatic adaptation to a current state of the network.
U.S. Pat. No, 5,687,175, entitled "Adaptive time division multiplexing communications protocol method and system" issued Nov. 11, 1997 to Rochester, et al., a communication protocol for collecting data from remote sensors via a wireless network is disclosed. The protocol disclosed in U.S. Pat. No. 5,687,175 uses a two-step polling technique. During the first step, the polling device simultaneously polls all remote stations enabling them to transmit their unique identifiers, if they need to transmit data. In response, those stations which have data, transmit their ID using a random access protocol. During the second step, the polling node polls the remote stations which have successfully transmitted their ID during the first step.
The two-step polling protocol of U.S. Pat. No. 5,687,175 has the drawback that it doesn't provide a high medium capacity utilization. This is because the high overhead of the two-step poling protocol reduces the medium capacity utilization. Another drawback is that real time data transmission may not be possible in some cases. This is because of the collisions that may occur which are associated with the random access during the first step of polling. The two-step polling protocol technique can not be used for high-efficiency, real-time transmission that adapts to variable traffic, distances, and speed of transmission.
U.S. Pat. No. 5,706,274 "CSMA with dynamic persistence" issued Jan. 6, 1998 to Angelico, et al., discloses a method for dynamically determining a persistence value, P, to increase capacity utilization of a media in a P-persistent Carrier Sense Multiple Access networks. While the method of U.S. Pat. No. 5,706,274 can be used for dynamic optimization of P and increasing the capacity utilization, it is not a collision-free technique, has a comparatively low capacity utilization and can not be used for real-time transmission.
U.S. Pat. No. 5,699,515 "Backoff scheme for access collision on local area network" issued Dec. 16, 1997 to Berkema et al., uses dynamic adaptation to the network load via variable random delay of transmitting packets. Each packet before transmission is delayed by a random delay value, selected from a variable backoff value. If during the delay, a packet from another node appears, or a collision occurs, the backoff value is increased. If a packet is transmitted successfully, the backoff value is decreased. The method of U.S. Pat. No. 5,699,515 presents a means for dynamic adaptation to some network variables; but it does not provide high-efficient collision-free transmission. Additionally, the method of U.S. Pat. No. 5,699,515 does not provide any means for adaptation to network distances or speed of transmission.
Conventional protocols and access methods have many drawbacks. They cannot be used for constructing collision-free, real-time multiple-access networks that have a limited latency and which provide high capacity utilization in variable network environments by dynamic adaptation to the network topology, traffic, transmission speed and channel lengths. Common collision-free MAC protocols (like token-ring, token-bus, polling etc.) have no means for adapting to the node activity, and cannot optimize MAC procedures to adjust to the current state of the network. Conventional collision-free protocols do not have a mechanisms for adaptation to bursty traffic, and therefore have a loss of capacity utilization; and hence an increase of the latency. Consequently, such protocols have some loss of capacity utilization, and, therefore, increase of latency.
What is desired is a high efficiency, collision-free multiple access method, which provides multiple access control with automatic adaptation to current network parameters.